package com.catmiw.csdn;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class T1 {
	private int pointscount;
	private int[][] costs;
	private List<int[]> resultlines;
	private int maxcost=0;
	private List<int[]> groups;
	
	public void addGroup(int p){
		groups.add(new int[]{p});
	}
	
	public int findPointInGroup(int p){
		for (int i=0;i<groups.size();i++){
			for (int j=0;j<groups.get(i).length;j++){
				if (groups.get(i)[j]==p)
					return i;
			}
		}
		
		return -1;
	}
	
	public void inputData(String filename){
		BufferedReader br=null;
		String str=null;
		try {
			br = new BufferedReader(new FileReader(filename));
			str=br.readLine();
			pointscount=Integer.parseInt(str);//读出有多少条点
			
			costs=new int[pointscount+1][pointscount+1];
			resultlines=new ArrayList<int[]>();
			groups=new ArrayList<int[]>();
			
			for (int i=0;i<pointscount*(pointscount-1)/2;i++){//读每条路径
				str=br.readLine();
				Scanner scanner=new Scanner(str);
				int begin=scanner.nextInt();//起点
				int end=scanner.nextInt();//终点
				if (begin>end){
					int t=begin;
					begin=end;
					end=t;
				}
				int done=scanner.nextInt();//已建/未建
				int cost=scanner.nextInt();//费用
				costs[begin][end]= (done==1?0:cost);//如果已建，可视为费用为0
				costs[end][begin]=costs[begin][end];
				if (maxcost<costs[begin][end])//记录最大费用
					maxcost=costs[begin][end];
				
				if (findPointInGroup(begin)<0){
					addGroup(begin);
				}
				if (findPointInGroup(end)<0){
					addGroup(end);
				}
			}
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		} finally {
			try {
				br.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}
	
	public int[] minCostInGroup(int b,int e){
		int[] line=new int[3];
		line[2]=maxcost;
		
		int[] begin=groups.get(b);
		int[] end=groups.get(e);
		
		for (int i=0;i<begin.length;i++){
			for (int j=0;j<end.length;j++){
				if (costs[begin[i]][end[j]]<=line[2]){
					line[2]=costs[begin[i]][end[j]];
					line[0]=begin[i];
					line[1]=end[j];
				}
			}
		}
		
		return line;
	}
	
	public void mergeGroup(int[] line){
		int bg=findPointInGroup(line[0]);
		int eg=findPointInGroup(line[1]);
		mergeGroup(bg,eg);
	}
	
	/*
	public void printGroups(){
		System.out.println("-----------------------");
		for (int[] p:groups){
			for (int x:p){
				System.out.print(x+"\t");
			}
			System.out.println();
		}
	}*/
	
	public void mergeGroup(int bg,int eg){
		int[] bgs=groups.get(bg);
		int[] egs=groups.get(eg);
		
		int[] now=new int[bgs.length+egs.length];
		System.arraycopy(bgs, 0, now, 0, bgs.length);
		System.arraycopy(egs, 0, now, bgs.length, egs.length);
		
		groups.remove(eg);
		groups.remove(bg);
		
		groups.add(now);
		
		//printGroups();
		
	}
	
	public void findMinCost(){
		List<int[]> lines=new ArrayList<int[]>();
		int[] line=null;
		
		for (int i=0;i<groups.size()-1;i++){
			for (int j=i+1;j<groups.size();j++){
				line=minCostInGroup(i,j);
				lines.add(line);
			}
		}
		
		Collections.sort(lines,new Comparator<int[]>(){
			public int compare(int[] o1, int[] o2) {
				return o1[2]-o2[2];
			}
		});
		
		line=lines.get(0);
		resultlines.add(line);
		
		mergeGroup(line);
		
		if (groups.size()==1){
			int sum=0;
			for (int i=0;i<resultlines.size();i++){
				sum+=resultlines.get(i)[2];
				System.out.println((resultlines.get(i)[0])+"\t"+resultlines.get(i)[1]+"\t"+resultlines.get(i)[2]);
			}
			System.out.println("最低成本："+sum);
		} else {
			findMinCost();
		}
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		T1 t=new T1();
		t.inputData("d:\\T1.txt");
		t.findMinCost();

	}

}
